LeetCode 891

发表于
本文字数： 3.3k | 阅读时长 ≈ 3 分钟

LeetCode #891. 子序列宽度之和

原题

给定一个整数数组 A ，考虑 A 的所有非空子序列。

对于任意序列 S ，设 S 的宽度是 S 的最大元素和最小元素的差。

返回 A 的所有子序列的宽度之和。

由于答案可能非常大，请返回答案模 10^9+7。

示例：

1
2
3
4
5
6
输入：[2,1,3]
输出：6
解释：
子序列为 [1]，[2]，[3]，[2,1]，[2,3]，[1,3]，[2,1,3] 。
相应的宽度是 0，0，0，1，1，2，2 。
这些宽度之和是 6 。

这是 第98场周赛 上的最后一题，是比较难的。

代码模板：

1
2
3
4
5
6
7
# 代码 - 0
class Solution:
    def sumSubseqWidths(self, A):
        """
        :type A: List[int]
        :rtype: int
        """

思路

题目要求一个数组的所有子数组的最大最小值的差之和。

对 Python ，有内建的 max() 函数用于求可迭代对象的最大元素。于是问题就只剩下如何获取 list A 的所有子集，得到 A 的所有子集，然后将所有子集的“宽度”相加、return 就行了。

对于求一个 list 的全部子集，有两种途径：

  1. Python 标准库给出了现成的函数供调用：itertools。
    本题要用到 combinations() 实际上是初始化了一个 combinations 对象，该对象是一个迭代器，示例如下：

    1
    2
    3
    4
    5
    6
    7
    # 代码 - 1
    for i in itertools.combinations([2,1,3], 2):
        print(i)
    # 输出：
    # (1, 2)
    # (1, 3)
    # (2, 3)

    这个迭代器的元素是 [2,1,3] 中两元素组合的所有情形组成的 tuple 。、

  2. 用递归或迭代等方法自己实现求得 list 子集的函数。

实现（思路1）

首先我们要写一个 width() 函数来求一个整数数组的宽度（题中所述列表中最大最小元素之差）：

1
2
3
4
5
6
7
8
# 代码 - 2
def sumSubseqWidths(A):
    """
    :type A: List[int]
    :rtype: int
    """
    def width(l):
        return max(l) - min(l)  # 一行就解决，max()对list、tuple等都可用

如上，7、8 两行即可实现，很简洁。

随后利用 itertools.combinations 对 A 进行迭代。由于 combinations 是指定元素个数的，我们使用两个 for 循环，第一个循环控制子集的长度，例如 A = [2,1,3] ，则子集长度可能为 1, 2, 3；第二个循环就遍历特定长度的子集，比如 代码 - 1 中写的 for i in itertools.combinations([2,1,3], 2):将遍历 (1, 2)(1, 3)(2, 3) 这三个 tuple。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 代码 - 3
def sumSubseqWidths(A):
    """
    :type A: List[int]
    :rtype: int
    """
    def width(l):
        return max(l) - min(l)
    def cal(l):
        import itertools  # 导入库
        r = 0
        for lenth in range(1, len(l)+1):  # 子集的长度从1 到 len(l)+1
            # sublist 实际上是一个个tuple
            for sublist in itertools.combinations(l, lenth):
                r += width(sublist)  # 调用我们写的 width()函数求宽度
        return r  # 返回函数计算结果
	return cal(A) % (10**9+7) # 返回题目计算结果

测试

代码最后面再加几行测试，注意代码不缩进：

1
2
3
4
5
6
7
# 代码 - 4
t = 1000 * time.time()
print(sumSubseqWidths([21,12,8,21,11,35,36,10,30,29,28,1,24,23,36,30,38,17,14,37]))
print("运行耗时{:.0f}ms".format(time.time()*1000-t))
# 输出：
# 33212097
# 运行耗时967ms

可见输出结果正确，但是耗时极长，无法通过LeetCode的测试，在 A 较长时此算法没有使用价值。不过想想也知道既然 combinations 是Python内建函数，想必已经在效率问题上做到几乎最好了吧，而967ms这一成绩所受限制是Python的基因。

实现（思路2）

自己实现求子集的函数，尽管效率很可能不如内建函数，但有重大的学习意义。这里仅简要讨论递归方法，若想深入研究或学习其他求子集算法可参考 CSDN博客：求一个集合所有子集的Python实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 代码 - 5
def sumSubseqWidths_2(A):
    """
    :type A: List[int]
    :rtype: int
    """
    def width(l):
        if not l:			# 这里与前面稍稍有点差异，因为l可能=[]
            return 0
        return max(l) - min(l)

    def get_subsets(l):       # 已知任意集合l及其元素之一e，有e与l-e的
        if len(l) == 0:       # 已知任意集合l及其元素之一e，有e与l-e的
            return [[]]       # 每一个子集相加，所得元素组成的集合即为l的子集
        subsets = []
        first_element = l[0]
        rest_list = l[1:]
        for partial_subset in get_subsets(rest_list):
            subsets.append(partial_subset)
            subsets.append([first_element]+partial_subset)
        return subsets

    def cal(l):
        r = 0
        for sublist in get_subsets(l):
            r += width(sublist)
        return r

    return cal(A) % (10**9+7)

测试

1
2
3
4
5
6
7
# 代码 - 6
t = 1000 * time.time()
print(sumSubseqWidths_2([21,12,8,21,11,35,36,10,30,29,28,1,24,23,36,30,38,17,14,37]))
print("运行耗时{:.0f}ms".format(time.time()*1000-t))
# 输出：
# 33212097
# 运行耗时1779ms

答案正确，但所耗时长为思路1的两倍。